#include <bits/stdc++.h>

// 生成随机数据,保存在文件finame中
void creatData(const char* finame, int count, int range = 100) {
  // 生成随机数据，将数据保存在指定文件中
  freopen(finame, "w", stdout);  // 将标准输出流重定向到文件“in.txt”
  srand(time(0));                // 使用当前时间作为随机数种子
  for (int i = 0; i < count; i++) {
    printf("%d ", rand() % range + 1);  // 随机保存到文件“in.txt”中
  }
  fclose(stdout);
}
// 读取文件中的数据到数组
void readData(const char* finame, int data[], int count) {
  freopen(finame, "r", stdin);
  for (int i = 0; i < count; i++) {
    scanf("%d", &data[i]);
  }
  fclose(stdin);
}
// 输出排序后的结果到文件
void writeData(const char* finame, int data[], int count) {
  freopen(
      finame, "a",
      stdout);  // 追加到一个文件。写操作向文件末尾追加数据。如果文件不存在，则创建文件。
  for (int i = 0; i < count; i++) {
    printf("%d ", data[i]);
  }
  fclose(stdout);
}
// 输出排序后的结果到文件（带有运行时间）
void writeData(const char* finame, int data[], int count, int begin, int end) {
  freopen(finame, "w", stdout);
  int time = (end - begin) / CLOCKS_PER_SEC;
  printf("begin:%d \nend:%d \ntime:%ds \n", begin, end, time);
  fclose(stdout);
  writeData(finame, data, count);
}

// 交换两个元素
void swap(int& a, int& b) {
  int t = a;
  a = b;
  b = t;
}

// 输出一个数组
void myprintf(int a[], int length) {
  for (int i = 0; i < length; i++) {
    printf("%d, ", a[i]);
  }
}

// 4、希尔排序
void shellSort(int data[], int n) {
  int i, j, gap, temp;
  // 进行分组，最开始时的增量（gap）为数组长度的一半
  for (gap = n / 2; gap > 0; gap /= 2) {
    // 对各个分组进行排序（自己选择排序方式）
    for (i = gap; i < n; i++) {
      // 此处采用的是插入排序（移动法，相比交换法能减少交换次数）
      j = i;
      temp = data[j];
      while (j > gap && temp < data[j - gap]) {  // 寻找插入位置，元素依次往后挪
        // 注意循环条件，防止数组越界
        data[j] = data[j - gap];
        j -= gap;
      }
      // 此时j即元素temp应该插入的位置
      data[j] = temp;
    }
  }
}
// 5、快速排序
void quickSort(int data[], int left, int right)  //快速排序
{
  if (left < right) {
    // Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1

    int i = left, j = right, x = data[left];
    while (i < j) {
      while (i < j && data[j] >= x)  // 从右向左找第一个小于x的数
        j--;
      if (i < j) data[i++] = data[j];

      while (i < j && data[i] < x)  // 从左向右找第一个大于等于x的数
        i++;
      if (i < j) data[j--] = data[i];
    }
    data[i] = x;
    quickSort(data, left, i - 1);  // 递归调用
    quickSort(data, i + 1, right);
  }
}

// 6、堆排序
void adjust(int* a, int i, int n) {
  // 调整堆
  int temp = a[i];
  for (int k = 2 * i + 1; k < n; k = k * 2 + 1) {
    if (k + 1 < n && a[k] < a[k + 1]) {  // 如果左孩子小于右孩子，j指向右孩子
      k++;
    }
    if (a[k] > temp) {  // 如果子节点大于有节点，将子节点的值赋值给父节点
      a[i] = a[k];
      i = k;
    } else {
      break;
    }
  }
  a[i] = temp;
}
void heapSort(int* a, int n) {
  // 构建大顶堆
  for (int i = n / 2 - 1; i >= 0; i--) {
    adjust(a, i, n);
  }
  for (int i = n - 1; i > 0; --i) {
    swap(a[0], a[i]);
    adjust(a, 0, i);
  }
}